#include<iostream>
#include<vector>
#include<string>
using namespace std;

//布尔类型的二维数组用来标记原始数组已经走过的位置
vector<vector<bool>> check;
vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};


//79.单词搜索
bool dfs(vector<vector<char>>& board,int i,int j,int pos,string word){
    //i,j表示当前原始数组中的位置行和列，pos表示现在需要找到目标字符串的第几个字符

    //结束条件
    if(pos==word.size()){
        return true;
    }

    for (int k = 0; k < 4;k++){
        int x = row[k], y = col[k];
        //判断四个方向移动是否越界
        if(i+x>=0&&i+x<board.size()&&j+y>=0&&j+y<board[i].size()){
            if(check[i+x][j+y]==false&&board[i+x][j+y]==word[pos]){
                check[i + x][j + y] = true;
                if(dfs(board,i+x,j+y,pos+1,word)==true){
                    return true;
                }
                //回溯
                check[i + x][j + y] = false;
            }
        }
    }
    //四个方向都没有找到，返回false
    return false;
}
bool exist(vector<vector<char>>& board, string word){
    //先初始化布尔数组
    check.resize(board.size());
    for (int i = 0;i<check.size();i++){
        check[i].resize(board[i].size());
    }

    //先在原始数组中找到目标字符串的第一个字符
    for (int i = 0;i<board.size();i++){
        for (int j = 0; j < board[i].size();j++){
            if(board[i][j]==word[0]){
                check[i][j] = true;
                if(dfs(board, i, j, 1, word)==true){
                    return true;
                }
                //回溯
                check[i][j] = false;
            }
        }
    }
    return false;
}


//1219.黄金矿工
//全局变量
int ret;
void dfs(vector<vector<int>>& grid,int i,int j,int path){
    //这里直接每次递归函数时，先比较当前值，一定能找到最大值
    ret = max(ret, path);

    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        if(x>=0&&x<grid.size()&&y>=0&&y<grid[i].size()){
            if(grid[x][y]!=0&&check[x][y]==false){
                path+=grid[x][y];
                check[x][y] = true;
                dfs(grid, x, y, paht);
                //回溯
                path -= grid[x][y];
                check[x][y] = false;
            }
        }
    }
}
int getMaximumGold(vector<vector<int>>& grid){
    //先初始化布尔数组
    check.resize(grid.size());
    for (int i = 0;i<check.size();i++){
        check[i].resize(grid[i].size());
    }

    //依次遍历原始数组中不为0的位置
    for (int i = 0; i < grid.size();i++){
        for (int j = 0; j < grid[i].size();j++){
            if(grid[i][j]!=0){
                check[i][j] = true;
                dfs(grid, i, j, grid[i][j]);
                //回溯
                check[i][j] = false;
            }
        }
    }

    return ret;
}

//不同路径3
int ans = 0;
void dfs(vector<vector<int>>& grid,int i,int j){
    //结束条件
    if(grid[i][j]==2){
        bool flag = true;
        //遍历数组判断是否所有的可走位置全部走过，如果全部走过说明是符合路径，路径个数加一
        for (int row = 0; row < grid.size();row++){
            for (int col = 0; col < grid[0].size();col++){
                if(grid[row][col]==0&&check[row][col]==false){
                    flag = false;
                    break;
                }
            }
        }
        if(flag==true){
            ans++;
        }
        return;
    }

    //当前位置四个方向移动
    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        //判断是否移动的位置越界
        if(x>=0&&x<grid.size()&&y>=0&&y<grid[i].size()){
            //判断移动的位置是否可以走并且没有走过
            if((grid[x][y]==0||grid[x][y]==2)&&check[x][y]==false){
                check[x][y] = true;
                dfs(grid, x, y);
                //回溯
                check[x][y] = false;
            }
        }
    }
}
int uniquePathsIII(vector<vector<int>>& grid){
    //先初始化布尔数组
    check.resize(grid.size());
    for (int i = 0;i<check.size();i++){
        check[i].resize(grid[i].size());
    }

    //依次遍历原始数组找到入口位置
    for(int i=0;i<grid.size();i++){
        for (int j = 0;j<grid[i].size();j++){
            if(grid[i][j]==1){
                check[i][j] = true;
                dfs(grid, i, j);
                //因为只有一个入口，所以不用回溯，直接结束循环
                break;
            }
        }
    }

    return ans;
}


int main(){

    return 0;
}